The field of the present invention pertains to computer implemented graphics. More particularly, the present invention pertains to a method and system for efficiently simplifying 3D tetrahedral models used in 3D volumetric representations.
Computer graphics are being used today to perform a wide variety of tasks. Many different areas of business, industry, government, education, entertainment, and most recently, the home, are tapping into the enormous and rapidly growing list of applications developed for today""s increasingly powerful computer devices. Graphical user interfaces have replaced textual interfaces as the standard means for user computer interaction.
Graphics have also become a key technology for communicating ideas, data, and trends in most areas of commerce, science, and education. Until recently, real time user interaction with three dimensional (3D) models and pseudo-realistic images was feasible on only very high performance workstations. These workstations contain dedicated, special purpose graphics hardware, and are typically very expensive. The spectacular progress of semiconductor fabrication technology has made it possible to do the same real time 3D animation, with color shaded images of complex objects, described by thousands of polygons, on rendering subsystems of only a few chips. The most recent and most powerful workstations are capable of rendering completely life-like, realistically lighted, 3D scenes.
In a 3D computer generated image, objects are typically described by data models. These models store descriptions of xe2x80x9cprimitivesxe2x80x9d (usually mathematically described polygons and polyhedra) that define the shape of the object, the object attributes, and the connectivity and positioning data describing how the objects fit together. The component polygons and polyhedra connect at common edges defined in terms of common vertices and/or enclosed volumes.
There are primarily two techniques used in 3D modeling; surface geometry modeling, and volumetric modeling. Surface geometry modeling is the more common of the two techniques. As is well known, in surface geometry modeling, primitives are used to define the surface of an object (e.g., a polygon mesh approximating the shape of the surface of an object). The polygons are textured, Z-buffered, and shaded/illustrated onto an array of pixels, creating a realistic 3D image. Volumetric modeling is the less common of the two techniques. Volumetric modeling is considerably more complex than surface geometry modeling.
The volumetric modeling, or volumetric representation of objects is typically specified in terms of a set of 3D xe2x80x9cvolumetric primitivesxe2x80x9d, which include tetrahedra, blocks, cylinders, cones, spheres etc., and a set of Boolean operators, for example union, intersection and difference. In typical applications, the volumetric primitive descriptions can be much more complex, including for example, ellipsoidal shapes or other xe2x80x9cquadricxe2x80x9d descriptions (e.g., quadratic descriptions which consists of a second order surface with variable parameters). The volumetric modeling of complex objects is used to implement volume visualization applications.
Volume visualization is widely recognized as one of the best ways of understanding increasingly large and complex data sets, such as for example, large and complex sets of observed or simulated scientific and engineering data. The more advanced volume visualization techniques, for example, present an entire data set at once and take advantage of the innate capabilities of the human visual system to distinguish depth and recognize patterns, trends, and anomalies in complex visual environments. Such volume visualization techniques often present data with a minimum of preprocessing and enable users to interpret that data by applying their own knowledge of the scientific or engineering processes that underlie it. Hence, for example, by magnifying the human intelligence applied to the interpretation process, volume visualization allows scientists and engineers to create better solutions faster and at lower cost than ever possible before.
To achieve its best results, volume visualization requires accurate, high fidelity volume after representation of objects. Many such objects require the generation of smooth surfaces, curves, and internal and external features. To realistically generate a real-world object, various subdivision or tessellation algorithms have been developed.
The tessellation/subdivision algorithms are generally a set of geometry based rules for increasing the number of primitives used to model an object. A computer system implements these rules in the process of computing the tessellation, using the rules to manipulate the primitives of the model. A complex volumetric representation can include many hundreds of thousands of primitives.
For example, in a typical tessellation technique, the primitives comprising a volumetric model (e.g., tetrahedra) are each divided into a plurality of xe2x80x9cdaughterxe2x80x9d to primitives. The daughter primitives share most of the characteristics of the xe2x80x9cparentxe2x80x9d primitive, however, their position and orientation in 3D space is influenced by the position and orientation of neighboring daughter primitives. The nature and degree of this influence is implementation specific, i.e., particular tessellation algorithms cause differing effects. Tessellation algorithms determine the placement of the vertices and edges of the daughter primitives. In so doing, a typical tessellation algorithm utilizes not only information regarding the parent primitive, but also information regarding the connectivity of the parent primitive with its neighboring primitives. The tessellation algorithm places and connects the daughter primitives in 3D space such that the primitive mesh becomes a smoother, less geometrically aliased representation of the real life object being modeled.
There exists several problems, however, with increasing the number primitives used to model volumetric 3D objects. One problem is the fact that increasing the number primitives in a model greatly increases the computational load on the computer system. In performing volumetric tessellation processing, the computer system needs to perform geometric manipulations on each of the primitives comprising the model, which can lead to severe computational loads. These computational loads often slow the graphics processing speed of the computer system. In addition to the computational loads caused by performing the tessellation itself, the computer system has a finite amount of memory space. Each primitive in the model has a number of attributes which need to be stored, e.g., the coordinates of each of the vertices of the primitive, the connective relationship of the primitive in relation to its neighbors, the orientation of the primitive in 3D space, and the like. Volumetric tessellation also reduces the number of objects a computer system can simultaneously store and manipulate, volumetric tessellation processing geometrically increases the number of primitives in a modeled object. The lack of memory resources is often a limiting factor in the graphics process. Hence, all though it is desirable to model an object with a large number of primitives in order to reduce geometric aliasing, increasing the number of primitives greatly stresses the computational resources of the computer system.
Thus, many applications require that some form of simplifying transformation be applied to a tetrahedral tessellation to facilitate easier manipulation by the computer system. For example, many adjacent cells of an xe2x80x9cover-tessellatedxe2x80x9d object can be collapsed to decrease the cell count (e.g., two adjacent primitives can often be collapsed into one reducing the minimal cell count from 10 to 5). Similarly, certain types of sub-volumes clipped to arbitrary densely tessellated surfaces (e.g., horizon surfaces in seismic data interpretation) can result in prohibitively large number of cells and may have to be simplified in order to facilitate further manipulation. As another example, the creation of multi-resolution models of volumetrically defined objects can also require smooth transformation between various tetrahedral decompositions. Such models can be used to improve rendering performance for large volumetric models of large complex data sets, or, for example, to facilitate hierarchical collision detection. Finally, combined with multi-resolution handing of large textures, tetrahedral mesh simplification can be used as an effective model compression technique and an aid for progressive transmission.
Thus, what is required is a method and system for efficiently implementing the simplification of a complex volumetric representation. What is required is a system for efficiently simplifying a tessellated volumetric model. The system should be able to reduce the number primitives used in a volumetric representation without causing excessive geometric aliasing. The system should be able to transform a tetrahedral volumetric representation to facilitate the operation of subsequent simplification algorithms. The system of the present invention provides a novel solution to the above requirements.
The present invention provides a method and system for efficiently implementing simplification algorithms for complex volumetric representations. The system of the present invention efficiently simplifies a tessellated volumetric model. The system of the present invention is able to reduce the number primitives used in a volumetric representation without causing excessive geometric aliasing. Additionally, the system of the present invention is able to transform a tetrahedral volumetric representation to facilitate the operation of subsequent simplification algorithms.
In one embodiment, the present invention is implemented as a computer implemented method for efficient simplification of tetrahedral meshes used in 3D volumetric representations, as performed in a 3D graphics computer system. The 3D graphics computer system implements a method for manipulating a volumetric model of a 3D object to simplify the volumetric model by reducing the number of primitives within the volumetric model. To implement the method, the computer system accesses a volumetric model of a 3D object. The 3D object is modeled using a large number of volumetric primitives. After accessing, the volumetric model is analyzed to identify a plurality of sets of adjacent primitives within the model for processing. For each set of identified adjacent primitives, the set of primitives is transformed within the volumetric model to facilitate the simplification of the model. The resulting transformed set of primitives are then stored. This process is carried through to completion, until the entire volumetric model has been processed. The resulting transformed volumetric model is then output for further processing or manipulation.
In this manner, the 3D graphics computer system is able to transform a tetrahedral volumetric representation of a 3D object or scene to facilitate the operation of subsequent simplification algorithms. The specific transformation process used on the sets of adjacent primitives can be based on adaptive subdivision, geometry decimation, sampling, or similar procedures.
Embodiments of the transformation processing apply one or more specific type of local transformation (e.g., as performed on adjacent sets of primitives). Such local transformations include, for example, Face Swap, Face Split, Edge Collapse, Vertex Split, Half-Edge Collapse, Vertex Insertion, Vertex Deletion. Additionally, the transformation process may be deterministic or stochastic, algorithmic or heuristic. Further, the end result of the transformation process may or may not preserve volumetric model topology. Various refinements of the transformation process can be implemented based on various topological, geometric, or per-vertex property preserving criteria. In addition to outputting the resulting transformed volumetric model, various error metrics can also be output.